#include <stdio.h>
#include <stdlib.h>
#define SIZE 6

int Graph[SIZE][SIZE];

/* path from 1 to SIZE */
int Path[SIZE];

void InitPath (void)
{
    for(int i = 0;i < SIZE;i++)
        Path[i] = i;
}

void InitGraph (void)
{
    for(int i = 0;i < SIZE;i++){
        for(int j = i+1;j < SIZE;j++)
            Graph[i][j] = 15-i-2*j;
        for(int j = 0;j < i;j++)
            Graph[i][j] = Graph[j][i];
        Graph[i][i] = 0;
    }
    InitPath();
}

void PrintGraph (void)
{
    for(int i = 0;i < SIZE;i++)
    {
        for(int j = 0;j < SIZE;j++)
            printf("%d\t",Graph[i][j]);
        printf("\n");
    }
}

int ScorePath (void)
/* score for the current path */
{
    int score = 0;
    for(int i = 0;i < SIZE-1;i++)
        score += Graph[Path[i]][Path[i+1]];
    score += Graph[Path[SIZE-1]][Path[0]];
    return score;
}

void swap (int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int ClimbStep (void)
/* climb for a step */
{
    int MinScore = 100000, CurScore, chg_a, chg_b;
    for(int i = 0;i < SIZE;i++)
        for(int j = i+1;j < SIZE;j++)
        {
            swap(&Path[i],&Path[j]);
            CurScore = ScorePath();
            if(CurScore < MinScore){
                MinScore = CurScore;
                chg_a = i;
                chg_b = j;
            }
            swap(&Path[i],&Path[j]);
        }
    swap(&Path[chg_a],&Path[chg_b]);
    return MinScore;
}

int ClimbHill (void)
/* climb the mountain */
{
    int MinScore = 100000, CurScore;
    while((CurScore = ClimbStep()) < MinScore)
        MinScore = CurScore;
    return MinScore;
}

int main (void)
{
    InitGraph();
    PrintGraph();
    printf("\n%d\n",ClimbHill());
    for(int i = 0;i < SIZE;i++)
        printf("%d\t",Path[i]);   
}